Alright, good morning. So welcome to the second lecture of the quantum computing course. In

today's lecture I will talk about composite quantum systems. So a quantum system that

is composed of two or more subsystems. Making use of the computational power that quantum

mechanical systems have if you use them as a computing as a processor. And in the second

part then I will start to discuss the first example of a quantum algorithm. It is faster

than a classical one. In this case not tremendously faster only by a factor two. But nonetheless

it shows all the essential ingredients of why quantum algorithms can be faster. And

it's an example where for the classical version there is really no way to speed it up. It's

really obvious the classical algorithm couldn't be faster than a classical algorithm. So before

talking about quantum computing, please remind me about the last lecture. So the last lecture

I will be giving you is a description of the quantum and quantum systems. So the focus

on the things that are the most important for this lecture. So of course we started

with the linear equation. That the time derivative of a state should be equal to minus i over

h bar Hamiltonian acting on that state. And so the main thing I pointed out there is that

this is a linear equation and this means that super positions exist. So a super position

meaning a state of the type that is a1 times phi 1 plus a2 times phi 2. So this means an

object in a quantum world can be in two states simultaneously. Yeah as an example an object

could be in two locations at the same time. In practice we never see these things because

of the perturbative effect that the environment has on whatever we would aim to study. At

least we don't see it in the microscopic world. So you haven't ever watched a football match

where the ball is in both goals at the same time. But such things are interesting for

quantum computing because as you can imagine it opens new possibilities as it would do

for football. A second consequence of the Schrodinger equation is that time evolution

is unitary. So the state psi at some time t is a unitary upper can be generated by applying

a unitary operator to the state at time zero. So unitary means the Hermitian conjugate is

the inverse so this evolution is reversible. Which will be important because it means whatever

algorithm you design for a quantum algorithm you need to look at reversible algorithms.

And the final thing was that the effect of a measurement is that you get an eigenvalue

say O nu of the observable that you are interested in. And it will mean that project the system

that you measured in the corresponding eigenstate which I also denote O nu.

So these are the main things that appeared in the repetition of quantum mechanics in

the last lecture. So now I want to talk about composite quantum systems. Maybe let me first

go on here.

So

this is important because the interesting consequences of super positions

only appear for multiple qubits. And the more the better. So basically for that reasons

we need a framework for describing composite quantum system. Composite quantum systems.

Okay and to keep things. So let me say for transparency. So to make like to not make

formulas look too complicated I consider bipartite here. So basically I want to look at a quantum

system that consists of two parts A and B. But this straightforwardly generalizes to

multiple subsystems.

First let me look at states. Possible states for such a composite quantum system. So the

state space, Hilbert space, is a direct product

of the subsystem Hilbert spaces. In a formula this would be the Hilbert space H is HA direct

product of HB. And okay so I tell you what this means in practice. So if we assume a

state on the subsystem A that may be some super position. So DA is the dimension of

the subsystem A. And so it can be a super position of the states in subsystem A. Okay

yeah so this states J could for example be the basis. In the case of a qubit it would

just be the zero and one. Yeah for a spin one half this is just a two dimension. So

DA would be two. And then I can write down a similar state for B. Here I call these coefficients